package com.aat.dxfy.game.blankwhite;

import java.util.ArrayList;
import java.util.List;

/**
 * 深度优先遍历算法,权值,给每个点赋权值
 * 
 * @author Brighter
 *
 */
public class DFS {

	private static Object[] vet; // 定义vet数组用来存放顶点信息
	private static int[][] array; // 定义邻接矩阵存放图的顶点信息
	private static int vexnum; // 存储边的条数
	private static boolean[] ifvisit;// 存放结点是否被访问过
	private static List<Object> list = new ArrayList<Object>(); // 定义一个临时的队列用来存放已经被访问过的结点

	public static void main(String[] args) {
		DFS map = new DFS(5);
		Character[] vet = { 'A', 'B', 'C', 'D', 'E' };
		map.addVet(vet);
		map.addEage(0, 1);
		map.addEage(0, 4);
		map.addEage(1, 3);
		map.addEage(2, 3);
		map.addEage(2, 4);

		System.out.println("深度优先遍历开始：");
		visited(0);
		ifvisit[0] = true;
		DFS.dfs(0);
	}

	public static void dfs(int k) {
		for (int i = 0; i < vexnum; i++) {
			if (array[k][i] == 1 && !ifvisit[i]) { // 判断是否被访问过，且其值是否是1
				ifvisit[i] = true;
				visited(i);
				for (int j = 0; j < vexnum; j++) {
					if (!ifvisit[j] && array[i][j] == 1) {
						ifvisit[j] = true;
						visited(j);
						dfs(j); // 下次循环从 vet[j]的链表开始循环
					}
				}
			}
		}

	}

	// 初始化图的节点
	private void addVet(Object[] object) {
		DFS.vet = object;
	}

	// 往临时队列里添加已经访问过的结点，并输出
	public static void visited(int k) {
		list.add(vet[k]);
		System.out.print("  -> " + vet[k]);
	}

	// 构建邻接矩阵，保存边的信息
	public void addEage(int m, int n) {
		if (m != n) {
			array[m][n] = 1;
			array[n][m] = 1;
		} else
			return;
	}

	// 图的初始化
	public DFS(int m) {
		vexnum = m;
		vet = new Object[m];
		array = new int[m][m];
		ifvisit = new boolean[m];
		for (int i = 0; i < m; i++) {
			ifvisit[i] = false;
			for (int j = 0; j < m; j++)
				array[i][j] = 0;
		}
	}

}